package com.hle.heap;
import java.util.Comparator;
import com.hle.printer.BinaryTreeInfo;


@SuppressWarnings("unchecked")

public class BinaryHeap<E> extends AbstractHeap<E> implements Heap<E>, BinaryTreeInfo {
	private E[] elements;

	private static final int DEFAULT_CAPACITY = 10;
	
	public BinaryHeap(E[] elements, Comparator comparator) {
		super(comparator);
        if (elements == null || elements.length == 0) {
			this.elements = (E[])new Object[DEFAULT_CAPACITY];
		}else {
            size = elements.length;
			int capacity = Math.max(DEFAULT_CAPACITY, elements.length);
			this.elements = (E[])new Object[capacity];
			for (int i = 0; i < elements.length; i++) {
				this.elements[i] = elements[i];
			}
            heapify();
		}
	}
		
	public BinaryHeap(E[] elements) {
		this(elements,null);
	}
	
	public BinaryHeap(Comparator comparator) {
		this(null,comparator);
	}
	
	public BinaryHeap() {
		this(null,null);
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		size = 0;
		for (int i = 0; i < size; i++) {
			 elements[i] = null;
		}
	}

	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		ensureCapacity(size +1);
		elements[size++] = element;
		shitUp(size - 1);
	}

	@Override
	public E get() {
		emptyCheck();
		return elements[0];
	}

	@Override
	public E remove() {
		emptyCheck();
		E root = elements[0];
		elements[0] = elements[size - 1];
		elements[size - 1] = null;
		size--;
		shitdown(0);
		return root;
	}

	@Override
	public E replace(E element) {
		// TODO Auto-generated method stub
		elementNotNullCheck(element);
		E top = null;
		if (size == 0) {
			elements[size++] = element;
		}else {
			top = elements[0];
			elements[0] = element;
			shitdown(0);
		}
		return top;
	}
		
	private void emptyCheck() {
		if (size == 0) {
			throw new IndexOutOfBoundsException("heap is empty");
		}
	}	
	
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}
	
	private void shitUp(int index) {
		E element = elements[index];
		while (index > 0) {
			int indexParent = ( index - 1 ) >> 1;
			E parent = elements[indexParent];
			if (compare(element, parent) <= 0 ) break;
			elements[index] = elements[indexParent];
			index = indexParent;
		}
		elements[index] = element;
	}
	
	private void shitdown(int index) {
		E element = elements[index];
		int  half = size >> 1; /// 非叶子节点
		while (index < half) {
            int childIndex = (index << 1) + 1;
			E child = elements[childIndex];
			int rightIndex = childIndex + 1;
			if (rightIndex <= size && compare(child, elements[rightIndex]) < 0) {
				child = elements[rightIndex];
				childIndex = rightIndex;
			}
			if (compare(child, element) <= 0) break;
			elements[index] = child;
			index = childIndex;
		}
		elements[index] = element;
	}
	
	private void heapify() {
		for (int i = (size >> 1) -1 ; i >= 0; i--) {
			shitdown(i);
		}
	}
	
	public void name() {
		System.out.println(1);
	} 
	
	private void ensureCapacity(int capacity) {
		int oldcapacity = elements.length;
		if (oldcapacity >= capacity)
			return;
		int newCapacity = oldcapacity + (oldcapacity >> 1);
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < elements.length; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
		System.out.println(oldcapacity + "扩容为" + newCapacity);
	}

	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		int index = ((int)node << 1) + 1;
		return index >= size ? null : index;
	}

	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		int index = ((int)node << 1) + 2;
		return index >= size ? null : index;
	}

	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
        return elements[(int)node];
	}
}
